package 递归回溯;

import com.alibaba.fastjson.JSON;

import java.util.*;

public class No39组合总和 {

    /**
     * 给定一个无重复元素的数组 candidates 和一个目标数 target ，
     * 找出 candidates 中所有可以使数字和为 target 的组合。
     * candidates 中的数字可以无限制重复被选取。
     *
     * 说明：
     * 所有数字（包括 target）都是正整数。
     * 解集不能包含重复的组合。 
     * 示例 1：
     * 输入：candidates = [2,3,6,7], target = 7,
     * 所求解集为：
     * [
     *   [7],
     *   [2,2,3]
     * ]
     */

    List<List<Integer>> lists=new ArrayList<>();
//    boolean[] flag;
//    Set<List<Integer>> set=new HashSet<>();
    int[] arr;

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        this.arr=candidates;
//        dg(target,0,new ArrayDeque<>());
        dgGood(target,0,new ArrayDeque<>());
        return lists;
    }

    /**
     * 更加优化的写法:排序后可以使用break剪枝,因为后面都再减都必定是负数了
     * 在力扣上没有快多少,实际上再看业务吧
     */
    private void dg(int target,int start,Deque<Integer> path){
        if(target<0)
            return;
        if(target==0){
            lists.add(new ArrayList<>(path));
            return;
        }
        /**
         * 写题时一定要想着如何才能变快!
         * 错误点:1.用set做判断,完全是没必要的2.循环起点为需要为i为错误点1做优化支撑
         */
        for (int i = start; i < arr.length; i++) {
            if(target-arr[i]<0)
                continue;
            target-=arr[i];
            path.addLast(arr[i]);
            dg(target,i,path);
            target+=arr[i];
            path.removeLast();
        }
    }

    private void dgGood(int target,int start,Deque<Integer> path){
        if(target==0){
            lists.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < arr.length; i++) {
            if(target-arr[i]<0)
                break;
            path.addLast(arr[i]);
            dgGood(target-arr[i],i,path);
            path.removeLast();
        }
    }

    public static void main(String[] args) {
        No39组合总和 n=new No39组合总和();
        List<List<Integer>> lists = n.combinationSum(new int[]{2,7,6,3,5,1}, 9);
        System.out.println(JSON.toJSONString(lists));
    }

}
